package org.renwei.alg.tree;

import com.google.common.collect.Lists;

import java.util.Arrays;
import java.util.List;

/**
 * Created by renwei on 16/8/25.
 * 使用数组实现的树
 */
public class MyTree<T> {

    private final int DEFAULT_SIZE = 2;
    private int size;       //数组长度
    private int count;      //节点个数
    private Object[] nodes; //节点存储

    public MyTree() {
        this.size = DEFAULT_SIZE;
        this.nodes = new Object[this.size];
        this.count = 0;
    }

    public MyTree(Node<T> root) {
        this();
        this.count = 1;
        this.nodes[0] = root;
    }

    public MyTree(Node<T> root, int size) {
        this.size = size;
        this.nodes = new Object[this.size];
        this.count = 1;
        this.nodes[0] = root;
    }


    /**
     * 添加一个节点，并指明父节点
     *
     * @param node
     * @param parent
     */
    public void add(Node<T> node, Node<T> parent) {
        node.setParent(this.position(parent));
        this.add(node);
    }

    /**
     * 获取整棵树有多少节点
     */
    public int getSize() {
        return this.count;
    }

    /**
     * 获取根节点
     *
     * @return
     */
    @SuppressWarnings("unchecked") public Node<T> getRoot() {
        return (Node<T>) this.nodes[0];
    }


    /**
     * 获取所有节点，以List的形式返回
     *
     * @return
     */
    @SuppressWarnings("unchecked") public List<Node<T>> getAllNodes() {
        List<Node<T>> list = Lists.newArrayList();
        for (int i = 0; i < this.count; i++) {
            list.add((Node<T>) nodes[i]);
        }
        return list;
    }

    /**
     * 获取树的深度，只有跟节点时为1
     *
     * @return
     */
    @SuppressWarnings("unchecked") public int getDepth() {
        int max = 1;
        if (null == this.nodes[0]) {
            return 0;
        }

        for (int i = 0; i < this.count; i++) {
            int deep = 1;
            int location = ((Node<T>) this.nodes[i]).getParent();
            while (-1 != location && null != this.nodes[location]) {
                deep++;
                location = ((Node<T>) this.nodes[location]).getParent();
            }
            if (max < deep) {
                max = deep;
            }
        }
        return max;
    }

    //获取节点在数组中的存储位置
    private int position(Node<T> node) {
        for (int i = 0; i < this.count; i++) {
            if (nodes[i] == node) {
                return i;
            }
        }
        return -1;
    }

    //添加节点
    private void add(Node<T> node) {
        check();
        if (null == this.nodes[count]) {
            nodes[count] = node;
        }
        this.count++;
    }

    //检测
    private void check() {
        if (this.count >= this.size) {
            this.enlarge();
        }
    }

    //动态扩展数组
    private void enlarge() {
        this.size += DEFAULT_SIZE;
        Object[] newNodes = Arrays.copyOf(nodes, this.size);
        Arrays.fill(nodes, null);

        this.nodes = newNodes;
    }
}
